﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Net;
using System.Text.RegularExpressions;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

     * */
    class Problem102 : IProblem
    {
        public string Calculate()
        {
            WebClient wc = new WebClient();

            string input = wc.DownloadString("http://projecteuler.net/project/triangles.txt");

            var result = Regex.Matches(input, "(-*[0-9]+,){5}-*[0-9]+").Cast<Match>()
                .Select(x => x.Value.Split(',')).Select(x => new Triangle(int.Parse(x[0]), int.Parse(x[1]), int.Parse(x[2]), int.Parse(x[3]), int.Parse(x[4]), int.Parse(x[5])))
                .Where(x => x.ContainsCentre()).Count();

            return result.ToString();
        }
    }

    struct Triangle
    {
        public int x1;
        public int x2;
        public int x3;
        public int y1;
        public int y2;
        public int y3;

        public Triangle(int x1, int y1, int x2, int y2, int x3, int y3)
        {
            this.x1 = x1;
            this.x2 = x2;
            this.x3 = x3;
            this.y1 = y1;
            this.y2 = y2;
            this.y3 = y3;
        }

        public bool ContainsCentre()
        {
            bool[] axes = new bool[4];
            axes[0] = axes[1] = axes[2] = axes[3] = false; //gore dolje lijevo desno

            IntersectAxes(x1, y1, x2, y2, axes);
            IntersectAxes(x1, y1, x3, y3, axes);
            IntersectAxes(x2, y2, x3, y3, axes);

            return axes[0] && axes[1] && axes[2] && axes[3];
        }

        void IntersectAxes(int x1, int y1, int x2, int y2, bool[] axes)
        {
            if (x1 == 0)
                if (y1 > 0)
                    axes[0] = true;
                else if (y1 < 0)
                    axes[1] = true;

            if (x2 == 0)
                if (y2 > 0)
                    axes[0] = true;
                else if (y2 < 0)
                    axes[1] = true;

            if (y1 == 0)
                if (x1 > 0)
                    axes[3] = true;
                else if (x1 < 0)
                    axes[2] = true;

            if (y2 == 0)
                if (x2 > 0)
                    axes[3] = true;
                else if (x2 < 0)
                    axes[2] = true;

            if (x1 == x2)
            {
                if (y1 * y2 < 0)
                {
                    if (x1 < 0)
                    {
                        axes[2] = true;
                    }
                    else
                    {
                        axes[3] = true;
                    }
                }
                return;
            }
            if (y1 == y2)
            {
                if (x1 * x2 < 0)
                {
                    if (y1 < 0)
                    {
                        axes[1] = true;
                    }
                    else
                    {
                        axes[0] = true;
                    }
                }
                return;
            }

            Fraction[] matrix1 = new Fraction[6];
            matrix1[0] = new Fraction(x1, 1);
            matrix1[1] = new Fraction(1, 1);
            matrix1[2] = new Fraction(y1, 1);
            matrix1[3] = new Fraction(x2, 1);
            matrix1[4] = new Fraction(1, 1);
            matrix1[5] = new Fraction(y2, 1);

            SolveMatrix(matrix1, 2);

            if (x1 * x2 < 0) //suprotne strane, negativan predznak
            {
                Fraction solution = matrix1[5];
                if (solution.Value > 0)
                {
                    axes[0] = true;
                }
                else if (solution.Value < 0)
                {
                    axes[1] = true;
                }
                else
                {
                    Console.WriteLine("nula");
                }
            }

            if (y1 * y2 < 0)
            {
                Fraction solution = matrix1[5];
                solution.Numerator *= -1;
                Fraction.Divide(solution, matrix1[2], out solution);
                if (solution.Value > 0)
                {
                    axes[3] = true;
                }
                else if (solution.Value < 0)
                {
                    axes[2] = true;
                }
                else
                {
                    Console.WriteLine("nula");
                }
            }
        }

        void SolveMatrix(Fraction[] matrix, int cardinality)
        {
            for (int j = 0; j < cardinality; j++)
            {
                Fraction divisor = matrix[j + j * (cardinality + 1)];
                for (int i = 0; i < cardinality + 1; i++)
                {
                    Fraction.Divide(matrix[i + j * (cardinality + 1)], divisor, out matrix[i + j * (cardinality + 1)]);

                }
                for (int k = 0; k < cardinality; k++)
                {
                    if (k == j)
                        continue;

                    Fraction factor = matrix[j + k * (cardinality + 1)];

                    for (int i = 0; i < cardinality + 1; i++)
                    {
                        Fraction multiplied;
                        Fraction.Multiply(matrix[i + j * (cardinality + 1)], factor, out multiplied);
                        Fraction.Subtract(matrix[i + k * (cardinality + 1)], multiplied, out matrix[i + k * (cardinality + 1)]);
                    }
                }
            }
        }

        public override string ToString()
        {
            return x1 + ":" + y1 + " " + x2 + ":" + y2 + " " + x3 + ":" + y3;
        }
    }
}
